/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/count-of-smaller-number
   @Language: C++
   @Datetime: 16-02-09 05:47
   */

// Method 1, Segment Tree, Time 413ms
class Solution {
	struct SegTreeNode{
		int first, last, count;     // range of num val, not pos
		struct SegTreeNode *left, *right;
		SegTreeNode(int first, int last, int count){
			this->first = first;
			this->last = last;
			this->count = count;
			left = right = NULL;
		}
		~SegTreeNode(){
			if (left) delete left;
			if (right) delete right;
		}
	};
	SegTreeNode *build(int first, int last,const vector<int> &hash){
		if (first>last) return NULL;
		SegTreeNode *root = new SegTreeNode(first,last,hash[first]);
		if (first==last) return root;
		root->left = build(first,first+(last-first)/2,hash);
		root->right = build(first+(last-first)/2+1,last,hash);
		root->count = root->left->count + root->right->count;
		return root;
	}
	int query(SegTreeNode *root,int first,int last){
		if (first>last || root==NULL || root->count==0) return 0;
		if (root->first==first && root->last==last)
			return root->count;
		int mid = root->first+(root->last-root->first)/2;
		if (mid<first) return query(root->right,first,last);
		if (mid>=last) return query(root->left,first,last);
		return query(root->left,first,mid)+query(root->right,mid+1,last);
	}

public:
	/**
	 * @param A: An integer array
	 * @return: The number of element in the array that 
	 *          are smaller that the given integer
	 * Tip: num val range [0,10000]
	 */
	vector<int> countOfSmallerNumber(vector<int> &A, vector<int> &queries) {
		// write your code here
		vector<int> hash(10001,0);
		for(int i=A.size(); i--; ++hash[A[i]]);
		SegTreeNode *root = build(0,10000,hash);
		vector<int> v(queries.size());
		for(int i=queries.size(); i--;)
			v[i] = query(root,0,queries[i]-1);
		delete root;
		return v;
	}
};

// Method 2, Binary Search, lower_bound, Time 295ms
class Solution {
public:
	/**
	 * @param A: An integer array
	 * @return: The number of element in the array that 
	 *          are smaller that the given integer
	 * Tip: num val range [0,10000]
	 */
	vector<int> countOfSmallerNumber(vector<int> &A, vector<int> &queries) {
		// write your code here
		sort(A.begin(),A.end());
		vector<int> v(queries.size());
		for(int i=queries.size(); i--;)
			v[i] = lower_bound(A.begin(),A.end(),queries[i])-A.begin();
		return v;
	}
};

